1. Field of the Invention
The present invention relates to distributed computer systems. More specifically, the present invention provides a method and an apparatus for detecting and correcting malicious data in an ad-hoc network without relying on an authentication infrastructure.
2. Related Art
Recent advances in microprocessor technologies have made it possible to incorporate significant amounts of computing power into vehicles, such as automobiles. For example, a typical new automobile presently has 40 to 50 microprocessors on-board, and high-end luxury vehicles include more than 100 microprocessors. At the same time, advances in wireless networking technologies are enabling these vehicles to efficiently communicate with each other.
These developments have lead to the development of Vehicular Ad-hoc NETworks (VANETs). VANETs enable geographically distributed vehicles to share data about vehicle locations and velocities, as well as information about weather, traffic and road conditions. This information can be used to facilitate dynamic route planning, safety and weather advisories, and road maintenance planning.
Unfortunately, a malicious vehicle which provides erroneous data can adversely affect nearby vehicles. For example, a malicious vehicle could report an illusory traffic jam on a freeway to cause other vehicles to travel on alternate routes. Diverting traffic in this way enables the malicious vehicle to avoid traffic on the freeway, but also causes unnecessary congestion on the alternate routes.
This problem can potentially be solved through network security mechanisms. The traditional approach to network security involves a key management solution which facilitates verifying data integrity and authenticating network “insiders.” Besides raising privacy concerns and being unwieldy for a VANET, this approach solves the wrong problem. In a VANET, far simpler attacks than data modification exist, such as, transmitting fraudulent data about road congestion or vehicle position. Furthermore, in large-scale VANETs there is no guarantee that previously honest nodes will not be corrupted in the future. Hence, security in a VANET depends upon solving the potentially more challenging problem of detecting and correcting malicious data.
Redundancy checks are commonly built into distributed systems to mitigate the threats posed by faulty or malicious participants. However, these redundancy checks can fail when a single adversary can present multiple distinct identities. These so-called “Sybil” attacks enable an adversary to assert virtual control over a substantial fraction of the system, contrary to the assumption on which redundancy checks are based.
A number of defenses have been proposed to guard against Sybil attacks, but they all have significant shortcomings in the context of a VANET (see [Newsome04] J. Newsome, E. Shi, D. Song and A. Perrig, “The Sybil Attack in Sensor Networks: Analysis and Defenses,” Proceedings of the Third Intl. Symposium on Information Processing in Sensor Networks, 2004.) These defenses and their shortcomings in the context of a VANET are briefly described below.                1. Radio resource testing assumes that a radio cannot send or receive simultaneously on more than one channel. However, it does not apply to VANETs, since a node can cheaply acquire multiple radios.        2. Registration assumes each participant is assigned a unique identity by a central, trusted authority. License plate numbers which identify vehicles are an example of that approach. However, providing unique electronic identifiers in a VANET raises more serious privacy concerns than physical license plates, and hence is unlikely to gain broad public acceptance. Furthermore, an approach based on assigning unique identifiers scales poorly (as demonstrated by the expense of administering license plate registrations). Hence, as the number of participants in the network grows larger, the task of maintaining and revoking identities becomes unmanageable.        3. Position verification operates by verifying the position of each node and assumes that identities that come from the same location belong to one and the same participant. However, such position verification techniques assume that nodes are static and hence do not apply to VANETs, because vehicles (nodes) are typically assumed to be in motion.        
Hence, what is needed is a method and an apparatus that effectively guards against malicious data attacks (e.g., Sybil attacks) in a vehicular ad-hoc network (VANET).